/**
 * [62] 不同路径
 * A(mn) = m!/(m-n)!
 * C(mn) = m!/n!(m-n)! = A(mn)/n!
 * @format
 * @lc app=leetcode.cn id=62 lang=javascript
 */

// @lc code=start
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
// 动态规划 O(mn)
var uniquePaths = function (m, n) {
    // paths 备忘录，记录每个网格到 Finish 的不同路径数
    const paths = []
    // 初始化 paths 右边缘和下边缘为 1
    for (let i = 0; i < m; i++) {
        paths.push([])
        for (let j = 0; j < n; j++) {
            if (j == 0 || i == 0) paths[i].push(1)
            else paths[i].push(paths[i - 1][j] + paths[i][j - 1])
        }
    }
    // 反向计算 paths
    // let index = m * n - m - n
    // while (index >= 0) {
    //     let [i, j] = [Math.floor(index / (n - 1)), index % (n - 1)]
    //     paths[i][j] = paths[i + 1][j] + paths[i][j + 1]
    //     index--
    // }
    return paths[m - 1][n - 1]
}

// 公式：排列组合求阶乘 O(n)
// var uniquePaths = function (m, n) {
//     const DOWN = n - 1
//     const RIGHT = m - 1
//     const TOTAL = m + n - 2
//     // if (TOTAL == 0) return 1
//     let [total_f, right_f, down_f] = [1, 1, 1]
//     for (let i = 1; i <= TOTAL; i++) {
//         total_f *= i
//         if (i == DOWN) down_f = total_f
//         if (i == RIGHT) right_f = total_f
//     }
//     return total_f / (right_f * down_f)
// }

// debugger
// let ways = uniquePaths(3, 7)
// console.log(ways)
// @lc code=end
